1
Best case: Big-Omega (Ω) — lower bound, e.g., Quick Sort O(n log n) when pivot always splits evenly
2
Average case: Big-Theta (Θ) often used — expected behavior over typical inputs
3
Worst case: Big-O — upper bound, e.g., Quick Sort O(n^2) with poor pivot choices

Difficulty: 5/10

Topics: time complexity analysis, algorithm performance, asymptotic analysis

0-2 years experience

1
If you implement a stack using an array that doubles its size when full, what are the best‑case and worst‑case time complexities for a push operation?
2
You need to search for a value in a sorted array using linear search. How do the best, average, and worst case runtimes differ?
3
When running binary search on a list of 1,000 items, what is the best‑case and worst‑case number of comparisons you might see?

2-5 years experience

1
Our search feature is slowing down under load. The algorithm is O(n) in the worst case but usually faster. How would you profile to understand if the average case is acceptable?
2
We switched from bubble sort to quicksort, but some inputs cause a performance regression. Explain how best, average, and worst‑case complexities guide your decision and what you’d do to mitigate the worst case.
3
A teammate argues that a worst‑case O(n²) algorithm is fine because the average case is O(n log n). How would you respond and what factors would you consider?

5-8 years experience

1
Design a pagination service that must meet a 200 ms SLA. How would you use best, average, and worst‑case analysis to choose data structures and caching strategies?
2
You need to implement a rate limiter that handles burst traffic. Discuss how worst‑case time complexity impacts latency and how you’d keep the worst case bounded.
3
When scaling a distributed sort, how do you account for worst‑case data skew versus average‑case performance, and what mitigations would you put in place?

8+ years experience

1
Our legacy system uses a recursive algorithm with exponential worst‑case time. We need a long‑term solution across teams. How would you evaluate the trade‑offs between a full rewrite for better worst‑case guarantees versus incremental optimization?
2
We are migrating to a new data store where query patterns have good average‑case latency but occasional pathological cases. How would you architect the system to protect against worst‑case spikes while keeping the migration manageable?
3
Across multiple services, worst‑case latency on a critical path is causing SLA breaches. How would you lead an organization‑wide effort to identify, measure, and improve worst‑case performance, balancing engineering effort and business risk?